This invention relates to digital information communication systems and, more particularly, to high throughput systems for communicating digital information. Specifically, the invention is directed to a method and apparatus for providing high throughput digital information communication in an asynchronous communication system in which digital information transceivers are connected in parallel to at least one communication circuit. More specifically, the invention is directed to a method and apparatus for acquiring a communication circuit in such a digital information communication system. The communication circuit acquisition method and apparatus in accordance with the invention are especially advantageous in a high throughput fault tolerant serial digital communication system, such as disclosed in the co-pending patent application of Stephen J. Sheafor and Ken K. S. Weng, entitled "Method and Apparatus For Fault Tolerant Serial Communication of Digital Information," U.S. Ser. No. 540,267, filed on Oct. 7, 1983, the disclosure of which is hereby incorporated by reference.
Generally, the architectures of known information processing systems, such as general purpose programmable digital computer systems, can be classified as either tightly coupled or loosely coupled, the trend being toward the loosely coupled architecture. A centralized memory is shared in a tightly coupled information processing system, and a central communication controller handles communication among the individual information processing elements on a synchronous basis. The burden on the central communication controller can be significant, which can impair the throughput of the information processing system.
A loosely coupled information processing system is also referred to as a distributed information processing system. The centralized memory allocated to each of the information processing elements in the tightly coupled information processing system is replaced by a different architecture. In a loosely coupled information processing system, memory is distributed throughout the information processing elements. That is, each information processing element includes a stand-alone memory and a communication controller. The communication controllers handle communication among the information processing elements through a communication network asynchronously.
The circuit implementation of the architecture in a loosely coupled information processing system can be less complicated than the circuit implementation of a tightly coupled information processing system due to a reduction in the complexity of the communication controller. Even more importantly, the proliferation of information processing elements, such as user terminals, add-on memory elements, and other input/output devices having stand-alone memory, which has occurred for extending the capabilities of the central information processing system, renders the information processing system conducive to a loosely coupled architecture.
Although the principles of the present invention are applicable to tightly coupled information processing systems, the method and apparatus for acquiring a communication circuit in accordance with the invention are particularly advantageous in loosely coupled information processing systems. Therefore, the communication circuit acquisition method and apparatus in accordance with the invention will be described by way of example in connection with loosely coupled information processing systems but should not be considered to be limited to use solely in a loosely coupled architecture.
There are various known techniques for communicating digital information in an information processing system. Several of these techniques are generally directed to communicating digital information in a tightly coupled information processing system.
One known technique for communicating digital information in an information processing system is referred to as polling. The polling technique for communicating digital information implies that the various information processing elements are connected to a central communication controller. The polling technique involves occasional or periodic communication between the central communication controller and each of the information processing elements so that the central communication controller can establish whether or not the information processing element requests communication with the central communication controller or any other information processing element. The polled information processing element is generally conditioned to transmit or receive digital information when the information processing element is polled during the polling procedure. The digital information is typically transmitted from one information processing element to the central communication controller and then to another information processing element in the event that communication is requested between the two information processing elements, rather than directly between the information processing elements. The polling technique assures that there is no simultaneous transmission of digital information by two or more information processing elements, that is, no collision of digital information, on the communication circuit. However, the polling technique does not efficiently utilize the available communication circuits and is not conducive to high throughput communication of digital information.
Another known technique for communicating digital information in an information processing system is time division multiplexing. The time division multiplexing technique for communicating digital information implies a central communication controller which assures synchronization so that each of the various information processing elements has access to the communication circuit during an assigned time slot for transmission of digital information. The remainder of the information processing elements receives the digital information on the communication circuit and responds to the communication if the communicated digital information is directed to that particular information processing element, such as by the detection of an address code. Collision is avoided since each information processing element can transmit digital information only during the assigned time slot. As in the case of the polling technique, however, the time division multiplexing technique does not efficiently utilize the communication circuits and does not enable high throughput digital information communication.
There are other known techniques for communicating digital information in a loosely coupled information processing system. These techniques comprise arbitration, multiple access, carrier sense multiple access (CSMA), carrier sense multiple access with collision detection (CSMA/CD), and token passing. These techniques for communicating digital information are generally used in decentralized information processing systems and are based on recognition of the fact that there might be contention between two or more information processing elements for a communication circuit, which can lead to a collision on the communication circuit that must be acted upon when such a collision occurs.
One known technique for communicating digital information in an information processing system is arbitration. Arbitration is a conceptually straightforward technique for communicating digital information. Various information processing elements are coupled to a central communication controller in parallel. When an information processing element is conditioned to transmit digital information to or receive digital information from another information processing element, the information processing element that is to initiate communication transmits a communication request to the central communication controller. The central communication controller receives such communication requests from each of the information processing elements as the need for communication arises and allocates a communication circuit or circuits in accordance with a predetermined protocol. The central communication controller arbitrates between contemporaneous requests from two or more information processing elements to assign access to the communication circuit or circuits, thereby avoiding simultaneous transmission by two or more information processing elements on a communication circuit. Unfortunately, the arbitration technique, although straightforward in concept, is difficult and expensive to implement and provides relatively low throughput due to the overhead associated with execution of the arbitration technique in order to avoid collision on the communication circuit or circuits.
There is also a finite probability with the arbitration technique that requests for communication can be simultaneously initiated by two or more information processing elements. In the event that simultaneous requests occur, that is, simultaneous contention for the communication circuit or circuits, the central communication controller likely responds to only one of the requests for access to the communication circuit or circuits, and the information processing element which does not gain access to the communication circuit or circuits attempts at a later time to obtain access to the communication circuit or circuits.
The known multiple access technique for communicating digital information does not attempt to determine the availability of the communication circuit for the communication of digital information from one information processing element to another. Rather, an information processing element which is conditioned to communicate with another information processing element merely transmits digital information on the communication circuit. If the information processing element which transmits the digital information does not receive a response from the information processing element to which the communication is directed, the original communication is reinitiated. The multiple access technique does not attempt to avoid collision of transmissions of digital information on the communication circuit, and the occurrence of such a collision results in receipt of an unintelligible communication by the information processing elements connected to the communication circuit.
The known carrier sense multiple access (CSMA) technique attempts to determine the availability of the communication circuit for communication of digital information. If the communication circuit is available, the information processing element which is conditioned to communicate with another information processing element initiates communication. If the communication circuit is busy, the information processing element that is to initiate communication awaits the availability of the communication circuit. The CSMA technique is characterized by the fact that the information processing element which is conditioned to communicate continuously monitors the communication circuit. This places a burden on the information processing element, which renders that information processing element unavailable for performing other information processing functions. Furthermore, there is a finite probability that two or more information processing elements sense that the communication circuit is available and simultaneously transmit digital information on the communication circuit, in which case a mechanism must be present to handle the appearance of unintelligible digital information on the communication circuit. Nevertheless, if communication over the communication circuit by the information processing elements is infrequent, then the probability of occurrence of collisions is low, and CSMA provides an effective technique for communication of digital information.
An extension of CSMA is the known CSMA with collision detection (CSMA/CD) technique. The CSMA/CD technique is described in Institute of Electrical and Electronic Engineers Publication No. 802. The CSMA/CD technique enhances the CSMA technique by the provision of a mechanism for checking digital information transmitted on the communication circuit in order to ascertain simultaneous transmission of digital information by two or more information processing elements on the communication circuit. In circumstances where the frequency of communication over the communication circuit is higher than anticipated in circumstances where CSMA is effective, CSMA/CD is an effective technique for communicating digital information. However, implementation of the CSMA/CD technique is more complex and expensive than implementation of the CSMA technique.
The token passing technique for communicating digital information is also described in Institute of Electrical and Electronic Engineers Publication No. 802. The token passing technique establishes a communication protocol within the information processing system so that the various information processing elements are configured in a ring or daisy chain. The availability of the communication circuit for communication by one information processing element to another is transferred from one information processing element to another. As in the case of the above-described polling technique and time division multiplexing technique, the token passing technique assures that no collision of digital information occurs on the communication circuit since only one information processing element is granted access to the communication circuit at a given time. The token passing technique, however, is inefficient unless the demand for access to the communication circuit is high. If the communication circuit is heavily loaded, then the token passing technique is advantageous because the token passing technique is deterministic of the availability of the communication circuit to the information processing element currently granted access to the communication circuit.
Each of the known techniques for communicating digital information in an information processing system appears to have certain advantages and certain disadvantages. In view of the severe limitation of the multiple access technique with regard to the inability to handle collisions and the limitation of the multiple access technique to information processing systems in which communication of digital information is frequent, the multiple access technique is not widely used. On the other hand, the token passing technique is often used in instances where the communication circuit is heavily loaded because of the deterministic characteristic of the token passing technique which assures that only one information processing element transmits over the communication circuit at a given time. The token passing technique, however, is not advantageous in other than instances where there is a heavily loaded communication circuit and can affect throughput in an information processing system, such as the high throughput fault tolerant serial digital communication system disclosed in the aforementioned Sheafor et al. patent application.
The Sheafor et al. patent application discloses a digital information communication system which provides high throughput fault tolerant serial digital information communication preferably characterized by full duplex, bidirectional communication of digital information in the form of messages being communicated in serial format at a first rate and half duplex, unidirectional communication of digital information in the form of large blocks of data being communicated in serial format at a second higher rate in order to enhance throughput. In view of the communication of large blocks of data at a higher rate, throughput over the communication circuits in the digital information communication system is improved, which reduces the average time needed by an information processing element to communicate digital information. This in turn reduces the load on the communication circuits and can reduce the need for the use of the token passing technique for communicating digital information. Consequently, the high throughput fault tolerant serial digital information communication method and apparatus disclosed in the Sheafor et al. patent application is susceptible to use of the CSMA or CSMA/CD technique. However, there is a severe disadvantage to use of the known CSMA or the known CSMA/CD technique for communicating digital information in that the processor of the information processing element which is conditioned to communicate with another information processing element must continuously monitor the communication circuit so as to ascertain when the communication circuit is available. This severely burdens the processor of the information processing element and precludes the processor from performing other information processing functions. This represents an inefficient overhead function for the processor included in the information processing element and results in a loss of the data processing power of the processor.